//==============================================================================
// Copyright (c) 2008-2013 Niall Ryan. All Rights Reserved.
//==============================================================================

#ifndef HYDRA_LOCKS_CLHLOCK_H
#define HYDRA_LOCKS_CLHLOCK_H 1

#include "hydra/atomic/Atomic.h"
#include "hydra/thread/ThreadLocal.h"

namespace Hydra
{
	/**
	 * CLH queue lock
	 * TODO: re-use nodes better, don't need L*N nodes but only L+N
	 */
	class CLHLock
	{
	public:
		CLHLock()
		{
			m_initNode.m_locked = false;
			m_tail = &m_initNode;
		}
		void lock()
		{
			Node* node = m_node->m_nodePtr;
            if (!node)
                node = m_node->m_nodePtr = &m_node->m_initNode;
			node->m_locked = true;
			Node* pred = m_tail.getAndSet(node);
			*m_pred = pred;
			Backoff backoff;
			while( pred->m_locked )
			{
				backoff.wait();
			}
		}
		void unlock()
		{
			Node* node = m_node->m_nodePtr;
			node->m_locked = false;
			m_node->m_nodePtr = *m_pred;
		}
	private:
		struct Node
		{
			Atomic<bool> m_locked;
		};

		//structure containing a node and pointer initialized to point to that node, used by ThreadLocal to give every thread an initial node
		struct InitNode
		{
			Node m_initNode;
			Node* m_nodePtr;
		};

		Node m_initNode;				//initial node for m_tail
		Atomic<Node*> m_tail;			//tail of the node queue
		ThreadLocal<InitNode> m_node;	//a node for every thread
		ThreadLocal<Node*> m_pred;		//predecessor pointer
	};
}

#endif
